package sort;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2023-01-16
 * Time: 13:51
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {5, 4, 1, 3};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    //基数排序（负数和小数的处理暂不考虑）
    public static void radixSort(int[] arr) {
        //先找到最大的数，确定为位数
        int maxVal = arr[0];
        for (int i : arr) {
            if (i > maxVal) {
                maxVal = i;
            }
        }
        //得到最大位数
        int maxLen = (maxVal + "").length();//转字符串，算长度
        //定义桶，即桶的容量
        int[][] bucket = new int[10][arr.length];
        //统计每个桶的数据个数
        int[] bucketElementCount = new int[10];
        //n为每轮的除数
        for (int i = 0, n = 1; i < maxLen; i++, n *= 10) {
            for (int j = 0; j < arr.length; j++) {
                //每个元素位数对应的桶
                int digitOfElement = arr[j] / n % 10;
                //放入对应的桶
                bucket[digitOfElement][bucketElementCount[digitOfElement]] = arr[j];
                bucketElementCount[digitOfElement]++;
            }
            //然后将桶中的数据依次放回原数组
            int index = 0;
            for (int j = 0; j < bucketElementCount.length; j++) {
                //判断桶是否为空
                if (bucketElementCount[j] != 0) {
                    for (int k = 0; k < bucketElementCount[j]; k++) {
                        arr[index++] = bucket[j][k];
                    }
                }
                //将桶内的数据归零，（此步不可以省略，否则会影响下一轮个数的统计）
                bucketElementCount[j] = 0;
            }
        }
    }


}
